﻿#include <iostream>
#include <assert.h>
#include <vector>
#define OPEN 0
#define LL long long 
using namespace std;

static const LL N = 8ll;
static LL a[N] = { 3ll, 1ll, 4ll, 2ll, 7ll, 5ll, 8ll, 9ll};
static LL tmp[N];

static LL fun(int l, int r) {
    if (l >= r)
        return 0ll;
    int mid = (l + r) >> 1;
    LL res = fun(l, mid) + fun(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else {
            tmp[k++] = a[j++];
            res += 0xffffffff & (mid - i + 1);
        }
    }
    while (i <= mid)
        tmp[k++] = a[i++];
    while (j <= r)
        tmp[k++] = a[j++];
    for (i = l, j = 0; i <= r; i++, j++)
        a[i] = tmp[j];
    return res;
}

int32_t main_ReversePairPractice() {
    memset(tmp, 0, sizeof(tmp));
    LL res = fun(0, 7);
    LL* p = a;
    return 0;
}

